#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/16 12:29
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _131_readBinaryWatch.py
from typing import List


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []

        def check_palindrome(string, left, right)->bool:
            while left<right:
                if string[left]!=string[right]:
                    return False
                left, right = left + 1, right - 1
            return True

        def dfs(star_index:int, path:List):
            if star_index==len(s):
                res.append(path[:])
                return

            for i in range(star_index, len(s)):
                if not check_palindrome(s, star_index, i):
                    continue
                path.append(s[star_index:i+1])
                dfs(i+1, path)
                path.pop()

        dfs(0, [])

        return res
